package com.dyz.leetcode._17_comprehensiveApplication;

public class _263_isUgly {
    // DFS
    public boolean isUgly1(int n) {
        if (n == 0) {return false;}
        return dfs(n);
    }

    // 判断整数 n 是否可以被 2、3、5 整除
    private boolean dfs(int n) {
        if (n == 1) {return true;}

        int[] factors = {2, 3, 5};
        for (int factor : factors) {
            if (n % factor == 0 && dfs(n / factor)) {
                return true;
            }
        }
        return false;
    }

    // 迭代
    public boolean isUgly(int n) {
        if (n == 0) {return false;}
        int[] factors = {2, 3, 5};
        for (int factor : factors) {
            while (n % factor == 0) {n /= factor;}
        }
        return n == 1;
    }
}
